//组合总和 力扣39
//回溯算法
//改进：剪枝 原本每一层的和要在遍历之后到下一层去判断
//           可以排序之后，在本层就先判断，若sum已经大于target,后续的肯定也会
//           大于target，本层就不再往后遍历
//           这样就能剪掉不必要的遍历
class Solution {
public:
	vector<int> path;
	vector<vector<int>> ans;
	int sum = 0;
	void backtracking(vector<int> candidates,int target,int startindex)
	{
		
		if(sum == target) 
		{
			ans.push_back(path);
			return;
		}
		
		for(int i = startindex; i < candidates.size() && sum+candidates[i]<=target; i++)
		{
			path.push_back(candidates[i]);
			sum += candidates[i];
			backtracking(candidates,target,i);
			path.pop_back();
			sum -= candidates[i];
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		sort(candidates.begin(),candidates.end());
		backtracking(candidates,target,0);
		return ans;
	}
};
